#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 500
#define MAXLENGTH 20 //最大行列

int x, y;//迷宫行列
int curstep = 1;//记录路径
int m[MAXLENGTH][MAXLENGTH];


typedef struct {
	int x;
	int y;
} posType; //坐标类型

typedef struct {
	int set;//步数
	posType seat;//
	int di;//方向 0右，1下，2左，3上
} SElemType; //栈元素类型

typedef struct {
	SElemType *top;
	SElemType *base;
} SqStack;

posType begin, end;

posType direc[4] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; //移动方向右下左上

void Push(SqStack *S, SElemType e) {//入栈
	*(S->top) = e;
	S->top++;
}
bool Pop(SqStack *S, SElemType *e) {//出栈
	if (S->base == S->top) {
		return false;
	}
	*e = *--S->top;
	return true;
}

bool StackEmpty(SqStack S) {
	if (S.top == S.base)
		return true;
	else {
		return false;
	}
}
void print(void) {//打印
	int i, j;
	for (i = 0; i <= x + 1; i++) {
		for (j = 0; j <= y + 1; j++) {
			printf("%3d", m[i][j]);
		}
		printf("\n");
	}
}

bool pass(posType b) {//判断是否是可通过的位置
	if (m[b.x][b.y] == 1) {
		return true;
	} else
		return false;
}
void Markprint(posType b) {//死胡同标记-1
	m[b.x][b.y] = -1;
}
void footprint(posType b) {
	m[b.x][b.y] = curstep;
}

void nextpos(posType *b, int di) {//根据di改变下一个位置
	b->x = b->x + direc[di].x;
	b->y = b->y + direc[di].y;
}
void InitStack(SqStack *s) {
	SElemType *p;
	p = (SElemType *)malloc(sizeof(SElemType) * MAXSIZE);
	if (!p)
		exit(-1);
	s->base = s->top = p;
}
void Init(void) {
	//迷宫初始化
	int i, j, x1, y1;
	scanf("%d %d", &x, &y);//迷宫行列
	for (i = 0; i <= x + 1  ; i++) {
		for (j = 0; j <= y + 1 ; j++) {
			m[i][j] = 1;//初始为一
		}
	}
	for (i = 0; i <= y + 1 ; i++) {
		m[0][i] = 0;
		m[x + 1][i] = 0; //上下围墙为0
	}
	for (i = 0; i <= x + 1 ; i++) {
		m[i][0] = 0;
		m[i][y + 1] = 0;
	}
	int wall = 0;
	printf("请输入墙的个数:");
	scanf("%d", &wall);
	printf("请输入墙的坐标\n：");
	for (i = 1; i <= wall; i++) {
		scanf("%d %d", &x1, &y1);
		m[x1][y1] = 0;
	}
	print();//迷宫结构打印
	printf("入口坐标：");
	scanf("%d" "%d", &begin.x, &begin.y);//初始位置
	printf("出口坐标：");
	scanf("%d" "%d", &end.x, &end.y);//终点位置
}

bool Mazepath(posType begin, posType end) {
	posType curpos = begin;
	SqStack s;//定义栈
	SElemType e;
	InitStack(&s);
	do {
		if (pass(curpos)) {
			footprint(curpos);//赋值当前位置
			e.set = curstep;//当前在栈的位置
			e.seat = curpos;//存放当前坐标
			e.di = 0;//从右开始
			Push(&s, e);//入栈
			curstep++;
			if (curpos.x == end.x && curpos.y == end.y) {
				return true;
			}
			nextpos(&curpos, e.di);//走向下一个点
		} else {
			if (!StackEmpty(s)) {
				Pop(&s, &e);
				curstep--;
				while (e.di == 3 && !StackEmpty(s)) {
					Markprint(e.seat);
					Pop(&s, &e);
					curstep--;
				}
			}
			if (e.di < 3) {
				e.di++;
				Push(&s, e);
				curstep++;
				curpos = e.seat;
				nextpos(&curpos, e.di);
			}
		}
	} while (!StackEmpty(s));
	return false;
}

int main() {
	Init();
	if (Mazepath(begin, end)) {
		printf("如图所示\n");
		print();
	} else
		printf("错误");
	return 0;
}
